package leetcode.code0154;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	public int findMin(int[] nums) {
		int len = nums.length;
		int l = 0;
		int r = len - 1;
		int ans = Integer.MAX_VALUE;
		while (l <= r) {
			int m = ((r - l) >> 1) + l;
			int L = nums[l];
			int M = nums[m];
			int R = nums[r];
			if (L == R) {
				l++;
				r--;
				ans = Math.min(L, ans);
			} else if (L > M) {// 大头落在L和M之间了，L~M没有单调性，M~R之间单调
				ans = Math.min(M, ans);
				if (M < L) {
					l += 1;
				} else {
					m -= 1;
				}
				r = m;
			} else {// L< M 大头落在M和R之间了， M~R之间没有单调性，L~M之间有单调性
				ans = Math.min(L, ans);
				if (M < R) {
					r -= 1;
				} else {
					m += 1;
				}
				l = m;
			}
		}
		return ans;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(1, this.findMin(HelpDebug.str2array3("[1,3,5]")));

	}

	@Override
	public void debug2() {
		HelpDebug.compare(0, this.findMin(HelpDebug.str2array3("[2,2,2,0,1]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();

	}

}
